iT邦幫忙

2022 iThome 鐵人賽

DAY 29
0
自我挑戰組

從leetcode學習資料結構和演算法系列 第 29

Day 29 Find First and Last Position of Element in Sorted Array

  • 分享至 

  • xImage
  •  

題目說明:給一個非遞減的矩陣(意即陣列當中第i+1個元素數值必>=第i個元素數值)和一個給定的目標值,要你求出該目標值第一次出現和最後一次出現的位置。如果都沒有出現,回傳[-1,-1],題目同時要求時間要控制在O(logn)

Case 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Case 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Case 3:
Input: nums = [], target = 0
Output: [-1,-1]

解題思路:看到要進行搜尋而且時間要控制在O(logn),想必是要使用binary seach(二分搜尋法),關於binary search可以參考之前撰寫的文章。這題比較麻煩的是要求第一次出現和最後一次出現的位置,因此將採用兩次binary search來找出位置。

附上程式碼以及註解
Java

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result=new int[2];//建立array儲存結果
        result[0]=firstpos(nums, target);//搜尋第一次出現的位置
        result[1]=lastpos(nums, target);//搜尋最後一次出現的位置
        return result;
    }
    public int firstpos(int[] nums,int target){
        int l=0;
        int r=nums.length-1;
        while (l<=r){
            int mid=(l+r)/2;
            if (nums[mid]==target){
                if (mid>0 && nums[mid-1]==target){
                    r=mid-1;//要判斷搜尋到的位置是否為第一次出現的位置
                }
                else{
                    return mid;
                }
            }
            else if(nums[mid]>target){
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        return -1;
    }
    public int lastpos(int[] nums,int target){
        int l=0;
        int r=nums.length-1;
        while (l<=r){
            int mid=(l+r)/2;
            if (nums[mid]==target){
                if (mid<nums.length-1 && nums[mid+1]==target){
                    l=mid+1;//要判斷搜尋到的位置是否為最後一次出現的位置
                }
                else{
                    return mid;
                }
            }
            else if(nums[mid]>target){
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        return -1;
    }
}

Python

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def firstpos():
            l=0
            r=len(nums)-1
            while r>=l:
                mid=(l+r)//2
                if nums[mid]==target:
                    if mid>0 and nums[mid-1]==target:
                        r=mid-1 #要判斷搜尋到的位置是否為第一次出現的位置
                    else:
                        return mid
                elif nums[mid]<target:
                    l=mid+1
                else:
                    r=mid-1
            return -1
        def lastpos():
            l=0
            r=len(nums)-1
            while r>=l:
                mid=(l+r)//2
                if nums[mid]==target:
                    if mid<len(nums)-1 and nums[mid+1]==target:
                        l=mid+1 #要判斷搜尋到的位置是否為最後一次出現的位置
                    else:
                        return mid
                elif nums[mid]<target:
                    l=mid+1
                else:
                    r=mid-1
            return -1
        return [firstpos(),lastpos()]

上一篇
Day 28 Pascal's Triangle
下一篇
Day 30 Is Subsequence
系列文
從leetcode學習資料結構和演算法31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言